package com.zhn;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 */

public class LongestPalindrome {
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len <= 1){
            return s;
        }
        //dp数组
        boolean[][] dp = new boolean[len][len];
        //初始化dp数组，单个字符一定是回文字符串
        for(int i = 0; i < len; i++){
            dp[i][i] = true;
        }
        //定义max值 保存最长回文长度
        int max = 1,start = 0;
        for(int j = 1;j < len; j++){
            //只遍历下三角部分就可以了，dp整个遍历会重复
            for(int i = 0; i < len-1&& i < j; i++){
                //如果最开始和最尾部的字符串不相等，绝对不是回文字符串
                if(s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else {
                    //也就是  dp的 j-1 - i+1 < 3
                    //else中已经判定i和j所在的字符相等，所以如果j-i<3则一定为回文字符，例如 aba,cac
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else {
                        //长度在范围外，就去确定子字符串
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                //更新回文最长的长度和最长回文数的起始位置，方便后续使用substring从原始字符串截取结果
                if(dp[i][j] && j-i+1 > max){
                    max = j-i+1;
                    start = i;
                }
            }
        }
        return s.substring(start,start+max);
    }
}
